/*
    树型dp-上

    前置知识: 
    讲解017、讲解018、讲解036、讲解037 - 二叉树基础内容
    讲解059 - 建图、链式前向星建图、拓扑排序
    讲解060 - 拓扑排序的扩展技巧，讲的题就是DAG图上的动态规划
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    本节课讲述最常见的树型dp问题，详解树型dp的解题套路

    下节课会讲述树型dp利用dfn序的内容

    注意：
    讲解060-拓扑排序的扩展技巧，DAG图上做动态规划（Directed Acyclic Graph），不要跳过
    树型dp中有关 换根dp 的内容，将放在【扩展】课程阶段讲述

    ================================================

    树
    头节点没有父亲，其他节点只有一个父亲的有向无环图，直观理解为发散状
    在树上，从头节点出发到任何节点的路径是唯一的，不管二叉树还是多叉树都如此

    树型dp在树上做动态规划，依赖关系比一般动态规划简单
    因为绝大部分多数都是父依赖子
    只是依赖关系简单，不代表题目简单

    树型dp套路
    1）分析父树得到答案需要子树的哪些信息
    2）把子树信息的全集定义成递归返回值
    3）通过递归让子树返回全集信息
    4）整合子树的全集信息得到父树的全集信息并返回

    ================================================

    题目1
    最大BST子树
    给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小
    其中，最大指的是子树节点数最多的
    二叉搜索树（BST）中的所有节点都具备以下属性：
    左子树的值小于其父（根）节点的值
    右子树的值大于其父（根）节点的值
    注意：子树必须包含其所有后代
    测试链接 : https://leetcode.cn/problems/largest-bst-subtree/

    ================================================

    题目2
    二叉搜索子树的最大键值和
    给你一棵以 root 为根的二叉树
    请你返回 任意 二叉搜索子树的最大键值和
    二叉搜索树的定义如下：
    任意节点的左子树中的键值都 小于 此节点的键值
    任意节点的右子树中的键值都 大于 此节点的键值
    任意节点的左子树和右子树都是二叉搜索树
    测试链接 : https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/

    ================================================

    题目3
    二叉树的直径
    给你一棵二叉树的根节点，返回该树的直径
    二叉树的 直径 是指树中任意两个节点之间最长路径的长度
    这条路径可能经过也可能不经过根节点 root
    两节点之间路径的 长度 由它们之间边数表示
    测试链接 : https://leetcode.cn/problems/diameter-of-binary-tree/

    ================================================

    题目4
    在二叉树中分配硬币
    给你一个有 n 个结点的二叉树的根结点 root
    其中树中每个结点 node 都对应有 node.val 枚硬币
    整棵树上一共有 n 枚硬币
    在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点
    移动可以是从父结点到子结点，或者从子结点移动到父结点
    返回使每个结点上 只有 一枚硬币所需的 最少 移动次数
    测试链接 : https://leetcode.cn/problems/distribute-coins-in-binary-tree/

    ================================================

    题目5
    没有上司的舞会
    某大学有n个职员，编号为1...n
    他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树
    父结点就是子结点的直接上司
    现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 
    但是如果某个职员的直接上司来参加舞会了
    那么这个职员就无论如何也不肯来参加舞会了
    所以请你编程计算邀请哪些职员可以使快乐指数最大，返回最大的快乐指数。
    测试链接 : https://www.luogu.com.cn/problem/P1352
    本题和讲解037的题目7类似
    链式链接 : https://leetcode.cn/problems/house-robber-iii/

    ================================================

    题目6
    监控二叉树
    给定一个二叉树，我们在树的节点上安装摄像头
    节点上的每个摄影头都可以监视其父对象、自身及其直接子对象
    计算监控树的所有节点所需的最小摄像头数量
    测试链接 : https://leetcode.cn/problems/binary-tree-cameras/

    ================================================

    题目7
    路径总和 III
    给定一个二叉树的根节点 root ，和一个整数 targetSum
    求该二叉树里节点值之和等于 targetSum 的 路径 的数目
    路径 不需要从根节点开始，也不需要在叶子节点结束
    但是路径方向必须是向下的（只能从父节点到子节点）
    测试链接 : https://leetcode.cn/problems/path-sum-iii/

*/